백준 17143번

오늘 풀어본 문제는 백준의 17143번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

낚시왕이 상어 낚시를 하는 곳은 크기가 $R \times C$ 인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 $(r, c)$ 로 나타낼 수 있다. $r$ 은 행, $c$ 는 열이고, $(R, C)$ 는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 처음에 $1$ 번 열의 한 칸 왼쪽에 있다. 다음은 $1$ 초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

낚시왕이 오른쪽으로 한 칸 이동한다.
낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

왼쪽 그림의 상태에서 $1$ 초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력

첫째 줄에 격자판의 크기 $R$, $C$ 와 상어의 수 $M$ 이 주어진다. $(2 \le R, C \le 100, 0 \le M \le R \times C)$

둘째 줄부터 $M$ 개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 $r$, $c$, $s$, $d$, $z$ $(1 \le r \le R, 1 \le c \le C, 0 \le s \le 1000, 1 \le d \le 4, 1 \le z \le 10000)$ 로 이루어져 있다. $(r, c)$ 는 상어의 위치, $s$ 는 속력, $d$ 는 이동 방향, $z$ 는 크기이다. $d$ 가 $1$ 인 경우는 위, $2$ 인 경우는 아래, $3$ 인 경우는 오른쪽, $4$ 인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

출력

낚시왕이 잡은 상어 크기의 합을 출력한다.

풀이과정

1번째 시도

문제를 읽으면서 힘든 구현 문제라는 것을 알 수 있었다. 우선 상어의 정보를 저장하는 구조체 Shark 를 만들고, 상어의 이동은 이동방향으로 좌표값을 더해준 뒤 왕복하는 데 필요한 칸 수의 나머지를 구하고, 그 값에 따라서 적절한 위치와 다음 이동 방향을 설정해주는 방식으로 구현하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;

struct Shark {
    int row;
    int col;
    int dr;
    int dc;
    int size;

    Shark() : row(0), col(0), dr(0), dc(0), size(0) {}

    Shark(int r, int c, int s, int d, int z) : row(r), col(c), size(z) {
        switch (d) {
            case 1:
                dr = -s;
                dc = 0;
                break;
            case 2:
                dr = s;
                dc = 0;
                break;
            case 3:
                dr = 0;
                dc = s;
                break;
            case 4:
                dr = 0;
                dc = -s;
                break;
            default:
                break;
        }
    }

    void move(int R, int C) {
        row -= 1;
        col -= 1;

        row = (row + dr) % (2 * (R - 1));
        col = (col + dc) % (2 * (C - 1));

        if (row < 0) {
            row += 2 * (R - 1);
        }

        if (col < 0) {
            col += 2 * (C - 1);
        }

        if (row >= R) {
            dr = -dr;
            row = 2 * (R - 1) - row;
        }

        if (col >= C) {
            dc = -dc;
            col = 2 * (C - 1) - col;
        }

        row += 1;
        col += 1;
    }

    void clear() {
        row = 0;
        col = 0;
        dr = 0;
        dc = 0;
        size = 0;
    }
};

void printGrid(const vector<vector<Shark>>& ocean, int R, int C);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int R, C, M;
    cin >> R >> C >> M;

    queue<Shark> sharks;
    vector<vector<Shark>> ocean(R+1, vector<Shark>(C+1, Shark()));

    for (int i=0; i<M; i++) {
        int r, c, s, d, z;
        cin >> r >> c >> s >> d >> z;

        Shark shark(r, c, s, d, z);

        sharks.push(shark);
        ocean[r][c] = shark;
    }

    int result = 0;
    for (int hunt=1; hunt<=C; hunt++) {
        for (int r=1; r<=R; r++) {
            if (ocean[r][hunt].size > 0) {
                result += ocean[r][hunt].size;
                ocean[r][hunt].clear();
                break;
            }
        }

        queue<Shark> newSharks;
        queue<pair<int, int>> check;

        while (!sharks.empty()) {
            Shark curr = sharks.front();
            sharks.pop();

            if (ocean[curr.row][curr.col].size > 0) {
                ocean[curr.row][curr.col].clear();
                curr.move(R, C);
                newSharks.push(curr);
            }
        }

        while (!newSharks.empty()) {
            Shark curr = newSharks.front();
            newSharks.pop();

            if (ocean[curr.row][curr.col].size == 0) {
                check.emplace(curr.row, curr.col);
            }
            if (ocean[curr.row][curr.col].size < curr.size) {
                ocean[curr.row][curr.col] = curr;
            }
        }

        while (!check.empty()) {
            pair<int, int> curr = check.front();
            check.pop();

            sharks.push(ocean[curr.first][curr.second]);
        }
    }

    cout << result;

    return 0;
}

void printGrid(const vector<vector<Shark>>& ocean, int R, int C) {
    for (int r=1; r<=R; r++) {
        for (int c=1; c<=C; c++) {
            cout << ocean[r][c].size << " ";
        }
        cout << "\n";
    }
}

제출한 결과 ‘틀렸습니다’ 가 떴다.

2번째 시도

로직을 되짚어 보는 과정에서 많은 구현 실수들이 있었다. 코드를 갈아엎는 과정에서 Ocean 클래스를 사용하는 대신 vector<vector<Shark>> 자료형을 직접 관리하는 방식으로 다시 구현하기로 했다…

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;

struct Shark {
    int row;
    int col;
    int dr;
    int dc;
    int size;

    Shark() : row(0), col(0), dr(0), dc(0), size(0) {}

    Shark(int r, int c, int s, int d, int z) : row(r), col(c), size(z) {
        switch (d) {
            case 1:
                dr = -s;
                dc = 0;
                break;
            case 2:
                dr = s;
                dc = 0;
                break;
            case 3:
                dr = 0;
                dc = s;
                break;
            case 4:
                dr = 0;
                dc = -s;
                break;
            default:
                break;
        }
    }

    void move(int R, int C) {
        row -= 1;
        col -= 1;

        row = (row + dr) % (2 * (R - 1));
        col = (col + dc) % (2 * (C - 1));

        if (row < 0) {
            row += 2 * (R - 1);
        }

        if (col < 0) {
            col += 2 * (C - 1);
        }

        if (row >= R) {
            dr = -dr;
            row = 2 * (R - 1) - row;
        }

        if (col >= C) {
            dc = -dc;
            col = 2 * (C - 1) - col;
        }

        row += 1;
        col += 1;
    }

    void clear() {
        row = 0;
        col = 0;
        dr = 0;
        dc = 0;
        size = 0;
    }
};

void printGrid(const vector<vector<Shark>>& ocean, int R, int C);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int R, C, M;
    cin >> R >> C >> M;

    queue<Shark> sharks;
    vector<vector<Shark>> ocean(R+1, vector<Shark>(C+1, Shark()));

    for (int i=0; i<M; i++) {
        int r, c, s, d, z;
        cin >> r >> c >> s >> d >> z;

        Shark shark(r, c, s, d, z);

        sharks.push(shark);
        ocean[r][c] = shark;
    }

    int result = 0;
    for (int hunt=1; hunt<=C; hunt++) {
        for (int r=1; r<=R; r++) {
            if (ocean[r][hunt].size > 0) {
                result += ocean[r][hunt].size;
                ocean[r][hunt].clear();
                break;
            }
        }

        queue<Shark> newSharks;
        queue<pair<int, int>> check;

        while (!sharks.empty()) {
            Shark curr = sharks.front();
            sharks.pop();

            if (ocean[curr.row][curr.col].size > 0) {
                ocean[curr.row][curr.col].clear();
                curr.move(R, C);
                newSharks.push(curr);
            }
        }

        while (!newSharks.empty()) {
            Shark curr = newSharks.front();
            newSharks.pop();

            if (ocean[curr.row][curr.col].size == 0) {
                check.emplace(curr.row, curr.col);
            }
            if (ocean[curr.row][curr.col].size < curr.size) {
                ocean[curr.row][curr.col] = curr;
            }
        }

        while (!check.empty()) {
            pair<int, int> curr = check.front();
            check.pop();

            sharks.push(ocean[curr.first][curr.second]);
        }
    }

    cout << result;

    return 0;
}

void printGrid(const vector<vector<Shark>>& ocean, int R, int C) {
    for (int r=1; r<=R; r++) {
        for (int c=1; c<=C; c++) {
            cout << ocean[r][c].size << " ";
        }
        cout << "\n";
    }
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

너무 힘든 문제였다. 이렇게 구현이 빡센 문제는 정말 간만이었다. CLASS 5 에서 구현문제를 만난다는 건, 정말 큰 마음의 준비를 해야하는 일임을 다시 한 번 상기시키게 되었다.

그리고 다 풀어놓고 생각해보니, ocean 이 굳이 상어 전체의 정보를 담을 필요없이 크기 정보만 담아도 되지 않나? 라는 생각이 든다. 만약 내가 제출한 코드를 활용하고 싶은데 이 점이 거슬리는 사람은, 직접 수정하길 바란다. ~~This is left as an exercise to the reader.~~

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/17143

← Previous Post Next Post →